Energy-Eficient CNN Computation on

• Energy-Eficient CNN Computation on Edge Devices under Stochastic Communication Delays

• 一、介绍
  • 许多物联网设备需要大量计算，通过云的方式降低功耗。但是受延迟限制、带宽限制以及云的算力限制。
  • 通过边缘计算解决问题时，考虑边缘设备 N，和物联网设备 D。D 只将计算密集型的任务给 N。
  • 1.1 overview
    • 本文提出了 edgewise 框架，以 cnn 算法为例，D 为无人机，N 为边缘云，CNN 的输入 (将被称为帧) 由一系列 CNN 层处理，其中每个层将在 D 或 N 上执行。D 在运行时决定哪个设备执行给定的 CNN 层。
    • 提出两种 EWR 模型，细粒度和粗粒度。细粒度是执行每个 CNN 层之前对网络延迟进行采样，粗粒度是在整个帧执行之前对网络延迟进行采样。通信延迟取决于传输的数据量 + 往返时间（RTT）的随机分量
    • 对于细粒度模型，提出了一种通用的非参数 (即没有关于分布的假设) 和数据驱动的解决方案，其中系统随时间的行为被建模为马尔可夫决策过程 (MDP)。MDP 的解决方案是一项策略，对于系统每一种状态，给出了选择 D 或 N 进行 CNN 层计算的决策。这个策略只需要离线运行一次，之后每次做决定之前进行查找，时间复杂度 o1，看来是个 hashmap。
    • 对于粗粒度模型，这是更复杂的细粒度模型的特例，提出了一种动态规划解决方案。这个最优解是由 D 在 O(L) 时间内在线构造的，其中 L 是 CNN 层数。它预先提供了完整的层分配，假设在执行帧期间测量的 RTT 没有变化。
    • 对于 D 与 N 的通信信道问题，如果出现 D 分配给 N 很多层，之后断开与 N 的连接了，那么这些计算就失效了，还不如 D 从一开始就自己计算。因此本文提出三种传输方案：保守方案：N 每执行一层，发回 D。乐观方案：N 仅在必要时发回 D。选择性方案：处理帧之前，基于网络稳定性的预测选择保守或者乐观
    • 我们在真实平台上进行了评估。程序为几种著名的 CNN 算法。通过重复直接测量获得计算延迟和功耗，用于优化确定粗粒度和细粒度的策略。同时和仅在 D 或者仅在 N 上计算进行对比，平均提高效果明显。此外，实施了两种最先进的转移方法，并与本文提出的方法的能量效率和开销进行比较。
  • 1.2 本文的贡献的总结
    • 一种细粒度的 MDP 模型，该模型考虑了受能量约束的嵌入式物联网设备 D 和无线可访问的附近加速器设备 N 之间的随机通信延迟，协同执行 CNN 应用 (由 D 托管)，目标是最小化 D 的能耗；
    • 最佳细粒度 MDP 解决方案 (以策略查找表的形式离线构建) 的轻量级使用，在 O(1) 时间内在线咨询，以确定给定当前观察到的网络延迟，哪个设备 D 或 N 将执行当前 CNN 层；
    • D 和 N 之间的粗粒度最佳层分配，在线性时间内在线构造，假设在给定帧开始处测量的网络延迟在 CNN 处理的该帧的持续时间内保持固定
    • 考虑到 D 和 N 之间无线链路的稳定性，研究了三种不同的方案，用于将层输出数据从 N 传输回 D (当 N 负责执行一个或多个 CNN 层时)。
  • 1.3 文章的组织
• 二、先前的工作
  • 一般都是高端设备，很少有低端受限设备
  • 之前有人用 java 调度图，并用 FM 启发式方法对图进行二分法，并基于此进行常规的目标检测。
  • 目前大部分采用 dnn（深度学习）的方式进行，对算力要求高。有人提出将整个执行状态封装为 web 应用程序来实现，这种方法将涉及整个模型发送到边缘服务器的高开销。
  • 有研究提出算法，仅将数据发送到云服务器以获得结果。但是延迟问题比较严重，要求连续帧不表现出突然的场景变化。
  • 以 dnn 的一层为粒度，在服务器和设备上协同执行 DNN 的框架是 Neurosurgeon 和 Edgnet。但这些方法的划分不一定在所有情况最优。jointDNN 首先计算发送不同层数据的开销，然后使用 0-1 ILP 进行最佳分配。这些方法都基于通信延时是固定的这一点，实际上对于无线系统中，通信延时很可能在短时间迅速变化。
  • 有人考虑了移动设备到云服务器代码加载过程中应用程序执行时间的变化。程序执行时间用版马尔可夫建模，根据模型对于不同状态的判断决定在本地还是服务器进行计算，但是没有涉及优化问题。
  • 有人解决了随机通信延迟、多个用户的任务部署问题。有人基于此，解决了用户服务质量最大化的问题。但是他们假设了所有计算发生在边缘服务器，并且重点是具有一般工作负载的分布式系统
  • 本文提出一种资源高度受限的嵌入式设备上执行 CNN 的策略，以 cnn 的每一层为粒度，考虑了通信的随机开销。
  • 工作创新点：1.低端物联网设备。2.MDP 建模考虑通信延迟。3.提出了最佳和轻量级解决方案。4.探索了不同方案的性能
• 三、系统模型
  • 应用模型：应用建模为有向无环图 DAG。节点可以进行拓扑排序，每个节点都有唯一的级别。CNN 可以建模为一个线图，每个层构成一个计算块。
  • 处理设备：IOT 设备 D，速度很快的计算设备 N。D 和 N 都能计算，D 根据需要将数据传给 N。
  • 3.1 通信延迟模型
    • 通信延迟受很多因素影响，入通信距离、数据包大小、通信负载相邻设备干扰等。可以表示为传输数据量/信道宽度（S/B）+ 往返时间或网络延迟（RTT）
    • 我们测量了有线 LAN 和无线 WIFI 的 RTT 他们和 CNN 的计算时间相比微不足道。
  • 3.2 能量模型
    • 我们希望确定应用计算块各在 D 和 N 之间的分配，以使得总能耗最低。
  • 3.3 数据传输方案
    • 针对于不同情况的网络，存在乐观调度模型和悲观调度模型，取决于网络的情况。
• 四、细粒度求解
  • 我们的方法是将应用程序执行的时间演化建模为马尔可夫决策过程 (MDP) 该决策可以进行离线求解，对于所有情况将任务分配给 D 或 N，我们将这些结果储存在表中，之后对于发生的情况直接去表中查询即可。时间复杂度 o1 在进行计算前，对于任务进行拓扑排序，将同一层次的任务合并为一个计算块。整个任务就变成了一条线。
• 五、粗粒度求解
  • RTT 在帧处理期间保持恒定的假设导致 MDP 公式的简化。 这是一个动态规划模型 复杂度 O(L)